Hash Table

Definition / 释义

哈希表（散列表）：一种用于快速存取数据的结构，通过哈希函数把“键（key）”映射到数组中的位置，从而实现平均情况下接近 O(1) 的查找、插入与删除。常见的冲突处理方式包括链地址法与开放定址法。

Pronunciation / 发音（IPA）

/hæʃ ˈteɪbəl/

Examples / 例句

She stored the usernames in a hash table for fast lookup.
她把用户名存进哈希表里，方便快速查找。

In many programming languages, dictionaries and maps are implemented using a hash table, which must handle collisions when different keys produce the same hash.
在许多编程语言中，字典和映射常用哈希表实现，而当不同键产生相同哈希值时，哈希表必须处理冲突。

Etymology / 词源

hash 原义与“切碎、剁碎、混杂”有关，后来在计算机领域引申为“把信息‘打散’成固定范围内的值”的过程，即哈希（散列）。table 指“表、表格”，在这里强调“按位置存放与查找”的结构。合在一起，hash table 就是“通过哈希把键映射到表中位置的数据表”。

Related Words / 相关词

• Hash
• Hashtable
• Hashing
• Collision
• Bucket
• Key
• Value
• Dictionary
• Map
• Set
• Array

Literary Works / 文献与作品中的用例

• Introduction to Algorithms（CLRS，《算法导论》）— 讨论散列表、哈希函数与冲突处理。
• The Art of Computer Programming, Volume 3: Sorting and Searching（Knuth，《计算机程序设计艺术》第3卷）— 系统介绍散列与检索方法。
• The C Programming Language（Kernighan & Ritchie，《C程序设计语言》）— 经典示例中涉及用散列表进行符号/关键字管理的思路与实现。